package com.tree;

public class MyTree implements MTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static TreeNode root;

    @Override
    public TreeNode creat() {
        TreeNode Node1 = new TreeNode(1);
        TreeNode Node2 = new TreeNode(2);
        TreeNode Node3 = new TreeNode(3);
        TreeNode Node4 = new TreeNode(4);
        TreeNode Node5 = new TreeNode(5);
        TreeNode Node6 = new TreeNode(6);
        TreeNode Node7 = new TreeNode(7);
        TreeNode Node8 = new TreeNode(8);

        Node1.left = Node2;
        Node1.right = Node3;
        Node2.left = Node4;
        Node3.left = Node5;
        Node3.right = Node6;
        Node4.left = Node7;
        Node7.right = Node8;
        return Node1;
    }

    @Override
    public void print(TreeNode root) {
        if (root == null) {
            return;
        }

        print(root.left);
        print(root.right);
        System.out.println(root.val);
    }

    @Override
    public int getsize(TreeNode root) {//获取树的节点数目
        if (root == null) {//树为空则返回0
            return 0;
        }
        //树不为空则递归左右子树的节点数目再加上本节点1
        return getsize(root.left) + getsize(root.right) + 1;
    }

    @Override
    public int hight(TreeNode root) {//树的高度
        if (root == null) {//树为空返回0
            return 0;
        }
        int left = hight(root.left);//不为空则递归左子树
        int right = hight(root.right);//不为空递归右子树
        int max = Math.max(left, right);//保存最大的高度
        return max + 1;//返回子树的最大高度再加本树的高度1
    }

    @Override
    public int leaves(TreeNode root) {
        int count=0;
        if(root==null){
            return 0;
        }
        if (root.left != null || root.right != null) {
            count=leaves(root.left)+leaves(root.right);
        }
        else {
            count++;
        }
        return count;
    }
}
